

"""5. 最长回文子串"""

class Solution5:

    """左右指针法"""
    def longestPalindrome(self, s: str) -> str:
        res = ''
        for i in range(len(s)):
            s1 = self.palindrome(s, i, i)
            s2 = self.palindrome(s, i, i+1)
            res = res if len(res) > len(s1) else s1
            res = res if len(res) > len(s2) else s2
        return res

    """在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串"""
    def palindrome(self, s: str, l: int, r: int) -> str:
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l+1: r]


    """方法1，中心扩散法"""
    def longestPalindrome1(self, s: str) -> str:
        len1 = len(s)
        res = ''

        for i in range(len1):
            left = i
            right = i
            # 向左扩散
            while left >= 0 and s[left] == s[i]:
                left -= 1
            res = s[left + 1: i + 1] if len(s[left: i + 1]) > len(res) else res
            # 向右扩散
            while right < len1 and s[i] == s[right]:
                right += 1
            res = s[i: right] if len(s[i: right]) > len(res) else res
            # 左右扩散
            while left >= 0 and right < len1 and s[left] == s[right]:
                right += 1
                left -= 1
            res = s[left + 1: right] if len(s[left + 1: right]) > len(res) else res
        return res


    """方法2，动态规划"""
    def longestPalindrome2(self, s: str) -> str:
        if not s:
            return ''
        len1 = len(s)
        f = [[False] * len1 for i in range(len1)]
        start = 0
        end = 0
        max_len = 0

        for j in range(1, len1):
            for i in range(0, j):
                if s[i] == s[j] and (j - i <= 2 or f[i + 1][j - 1]):
                    f[i][j] = True
                    if j - i + 1 > max_len:
                        max_len = j - i + 1
                        start = i
                        end = j
        return s[start: end + 1]


if __name__ == '__main__':
    sl = Solution5()
    # print(sl.longestPalindrome2('"babad"'))
    f = [[False] * 2 for i in range(3)]
    print(f)
    print(f[0])